/**
 * Dijkstra 算法实现
 * 求最短路径
 */


import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;

public class DijkstraTools {
    public int dijkstraFindShortestPath(String src, String dest, AdjacencyMatrix adjacencyMatrix) {
        SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        // 添加顶点
        String[] names = adjacencyMatrix.getMatrixName();
        for (String name : names) {
            graph.addVertex(name);
        }

        for (int i = 0; i < adjacencyMatrix.getNumVertices(); i++) {
            for (int j = 0; j < adjacencyMatrix.getNumVertices(); j++) {
                if (adjacencyMatrix.getWeight(i, j) != 0) {
                    DefaultWeightedEdge edge = graph.addEdge(adjacencyMatrix.getNameFromIndex(i), adjacencyMatrix.getNameFromIndex(j));
                    graph.setEdgeWeight(edge, adjacencyMatrix.getWeight(i, j));
                }
            }
        }

        DijkstraShortestPath<String, DefaultWeightedEdge> dijkstra = new DijkstraShortestPath<>(graph);

        double shortestPathLength = dijkstra.getPathWeight(src, dest);

        // 输出最短路径长度
        System.out.println("Shortest path length from " + src + " to " + dest + ": " + shortestPathLength);

        // 获取最短路径的顶点列表
        System.out.println("Shortest path from " + src + " to " + dest + ": " + dijkstra.getPath(src, dest));

        return Double.isInfinite(shortestPathLength) ? -1 : (int) shortestPathLength;
    }
}
